// hdu3401
// 题意：给定n天的股票行情，第i天买（卖）一支股票需要的（获得的）钱，
//       第i天股票交易的限制数目（买卖各有限制）。一共不能持有超过maxp
//       支股票，如果在第i天交易，那么必需在i+w+1天或者之后才能再交易。
//		 初始有无数的钱，问最多可以获益多少。
//
// 题解：考虑第i天有j支股票f[i][j]，如果不交易那么就从f[i-1][j]转移，
//       然后买卖是对称的，我们讨论下卖的。
//       f[i][j] = max{f[i-w-1][k] + (k - j) * SPi}
//       上式是说从i-w-1天（这个不难理解，可以反过来往后推就容易明白了），
//       k支股票卖出(k-j)支股票，价格是SPi的最大获益，且要满足限制。我们
//       改写下max里面的式子，即：
//       (f[i-w-1][k]+k*SPi) - j*SPi
//       后面是固定的，只需要求前面的最大值，且要满足卖出股票数目的限制，
//       这个很容易用个单调队列维护，就是维护最大值递减。
//       然后买入是类似的，一个要从后往前，一个从前往后。
// 统计：296ms, 1h20min, 1a
//
// run: $exec < input
// opt: 0
// flag: -g
#include <cstdio>
#include <algorithm>

struct trade
{
	int sp, bp, sl, bl; // sell price, sell limit, buy
};

struct state
{
	int v, p;
};

int const inf = 1 << 30;
int const maxn = 2100;
int f[maxn][maxn];
state monoq[4 * maxn];
trade da[maxn];
int n, maxp, w;

int main()
{
	int T;
	std::scanf("%d", &T);
	while (T--) {
		std::scanf("%d %d %d", &n, &maxp, &w);
		for (int i = 1; i <= n; i++)
			std::scanf("%d %d %d %d", &da[i].bp, &da[i].sp, &da[i].bl, &da[i].sl);

		for (int i = 1; i <= maxp; i++) f[0][i] = -inf;
		f[0][0] = 0;

		for (int i = 1; i <= n; i++) {
			for (int j = 0; j <= maxp; j++)
				f[i][j] = f[i - 1][j];

			int head = 1, tail = 0, t = std::max(i - w - 1, 0);
			// sell
			for (int j = maxp; j >= 0; j--) {
				while (head <= tail && monoq[head].p - j > da[i].sl) head++;
				state now;
				now.v = f[t][j] + j * da[i].sp; now.p = j;
				while (head <= tail && now.v >= monoq[tail].v) tail--;
				monoq[++tail] = now;
				f[i][j] = std::max(f[i][j], monoq[head].v - j * da[i].sp);
			}

			head = 1; tail = 0;
			// buy
			for (int j = 0; j <= maxp; j++) {
				while (head <= tail && j - monoq[head].p > da[i].bl) head++;
				state now;
				now.v = f[t][j] + j * da[i].bp; now.p = j;
				while (head <= tail && now.v >= monoq[tail].v) tail--;
				monoq[++tail] = now;
				f[i][j] = std::max(f[i][j], monoq[head].v - j * da[i].bp);
			}
		}

		/*
		for (int i = 1; i <= n; i++) {
			for (int j = 0; j <= maxp; j++) std::cout << f[i][j] << ' ';
			std::cout << '\n';
		}
		*/

		int ans = 0;
		for (int i = 0; i <= maxp; i++)
			 ans = std::max(ans, f[n][i]);
		std::printf("%d\n", ans);
	}
}

